public class code7_1 {
    //重写
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ret = new ArrayList<>();
        //1.排序
        Arrays.sort(nums);

        //2.固定第一个数nums[i]
        for(int i=0;i<n-2;) {
            //优化：当第一个数都为正数，直接不用继续了
            if(nums[i]>0) break;
            //转为两数之和：双指针
            int left=i+1,right=n-1,target=-nums[i];
            while(left<right) {
                int sum = nums[left] + nums[right];
                if(sum<target) left++;
                else if(sum>target) right--;
                else {
                    //找到了：nums[left] nums[right] target
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[left],nums[right],nums[i])));
                    //注意：这里和找两数之和不一样，这里不是直接返回，所以left和right还要继续变化
                    left++;right--;
                    //去重nums[left] nums[right]
                    while(left<right && nums[left]==nums[left-1]) left++;
                    while(left<right && nums[right]==nums[right+1]) right--;
                }

            }
            //去重target：nums[i]也可能重复
            i++;//add后i需要++
            while(i<n && nums[i]==nums[i-1]) i++;
        }
        return ret;
    }
}
